1. Technical Field
The present invention relates in general to the display of lines in a computer display system and in particular to a method and system for antialiasing lines displayed in a raster format within a computer display system. Still more particularly, the present invention relates to a method and system for antialiasing lines by generating an antialiased pixel approximation of a line in a computer display system.
2. Description of the Related Art
Visual display clarity is a problem faced by computer system developers. Graphics, including the set of text characters, are typically displayed using a raster image. The raster image is a rectangular array of rectangular picture elements known as pixels. Pixels are arranged on the computer display screen in rows and columns.
Image clarity problems typically occur when a continuous image is displayed using discrete pixels. The problem is most visible in the non-vertical and non-horizontal parts of a graphic image. For example, a line that is neither vertical nor horizontal will look jagged or stair-stepped because the line is constructed of rectangular pixels. This problem is called aliasing.
One method of solving aliasing problems is to employ a display with a greater number of pixels per square inch. With a higher resolution display, the stair-steps are smaller and therefore less noticeable. This solution, however, is expensive because of the high cost of high resolution displays. This option may not always be possible because of limited speed capability of the electronic components utilized in the display.
Another method of anti-aliasing involves modifying or blurring the pixels in the region near the jagged edge of the graphic image. Blurring the jagged edges reduces the contrast and makes the jagged edges less noticeable. In the edge blurring technique, both the brightness and color of the graphic image, and the background behind the image, may be considered when computing the new brightness and color of pixels near the jagged edge of the graphic image.
In converting a line into coordinates for pixels on a two-dimensional raster grid, the basic strategy employed by typical line scan-conversion algorithms is to increment x and calculate y=mx+b. A pixel is selected at (x, ROUND (y)) where ROUND (y) is a function that determines the y coordinate of the pixel closest to the y value calculated. These x and y values correspond to points on a grid wherein the intersection of x and y values associated with grid points are often referred to as "picture elements" or "pixels".
Most conventional raster displays rasterize a continuous line one pixel at a time, with each pixel being generated in sequence. Bresenham's algorithm is perhaps the most widely used algorithm for presenting lines on a raster display Bresenham's algorithm is explained in many computer graphics text books. For example, a description of the algorithm, as well as its derivation, are presented at pages 71-78 of Computer Graphics: Principles and Practice by Foley, Van Dam, Feiner, and Hughes, Addison-Wesley Publishing Company, Inc. (2d Ed. 1990), which is incorporated herein by reference.
Bresenham's algorithm determines a running error term as well as correction terms to be applied to the running error term as various pixel locations are chosen to represent the line. The initial error term and each of the correction terms is determined from the total x and y displacements traversed by the line. For each particular pixel, the error term associated with that pixel reflects the amount that the pixel deviates from the true line location. As a result, error terms for various pixels may be utilized to determine which pixels are closest to the actual line.
As pixel locations are sequentially selected and the algorithm is reiterated to select subsequent pixel locations, an appropriate error term is added to the running error term to account for changes in the error term produced by selecting the previous pixel location. Bresenham's algorithm is continued until the end of the line is reached and the last pixel location is selected.
An inherent problem with drawing a Bresenham line is that it appears very rough or jagged. Additionally, presently available methods and systems do not display Bresenham lines with as much precision as desired since they utilize integer endpoints.
Therefore, it would be desirable to have a method and system for producing lines that are visually smooth and positioned accurately with respect to subpixel endpoints.